import java.util.PriorityQueue;

public class LC23 {
    class Status implements Comparable<Status> {
        int val;
        ListNode node;

        public Status(int val, ListNode node) {
            this.val = val;
            this.node = node;
        }

        @Override
        public int compareTo(Status o) {
            return this.val - o.val;
        }
    }

    PriorityQueue<Status> listQueue = new PriorityQueue<>();

    public ListNode mergeKLists(ListNode[] lists) {
        ListNode head ;
        ListNode curr = new ListNode(-1);
        head = curr;
        for (ListNode nowNode : lists) {
            listQueue.offer(new Status(nowNode.val, nowNode));
        }
        while (!listQueue.isEmpty()) {
            Status temp = listQueue.poll();
            curr.next = temp.node;
            if (temp.node.next != null) {
                listQueue.offer(new Status(temp.node.next.val, temp.node.next));
            }
            curr = curr.next;
            curr.next = null;
        }
        return head.next;
    }
}
